#include <stdio.h>
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
#include<fstream>
#include <sstream>
#include<stack>
#include <ctime>

using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")

// 判断一个字符串是否为一个数字,如果是返回它
bool JudgeNum(string str, int &iTmp) {
    bool bNum = true;
    string::size_type szSize = str.size();
    for (int i = 0; i < szSize; ++i) {
        char ch = str.at(i);
        if ((ch < '0') || (ch > '9')) {
            bNum = false;
            break;
        }
    }
    if (bNum) {
        istringstream iss(str);
        iss >> iTmp;
    }
    return bNum;
}

void shellSort(int arr[], int n) {
    int tmp = 0;
    int step = n / 2;
    while (step) {
        for (int i = step; i < n; i++) {
            tmp = arr[i];
            int j = i;
            while (j >= step && tmp < arr[j - step]) {
                arr[j] = arr[j - step];
                j -= step;
            }

            arr[j] = tmp;
        }

        step = step / 2;
    }
}

int division(vector<int> &nums, int left, int right) {// 选一个位置作为基准值，使排序后的数组：
    // 左边的数都小于它，右边的数都大于他
    // 随机选择基准可以提高性能
    int base = nums[right];
    while (left < right) {

        while (left < right && nums[left] <= base) {
            left++;
        }
        nums[right] = nums[left];

        while (left < right && nums[right] >= base) {
            right--;
        }
        nums[left] = nums[right];
    }
    nums[right] = base;
    return right;
}

void FeidiguiQuickSort(vector<int> &nums)//非递归
{
    stack<int> st;
    // 如果中轴数索引两个分区存在,则将起点和终点入栈.
    int right = nums.size() - 1;
    if (right > 0) {
        st.push(0);
        st.push(right);
    } else {
        return;
    }
    // 从栈里面取出序列并找到该序列中轴数的正确索引
    while (!st.empty()) {
        int r = st.top();
        st.pop();
        int l = st.top();
        st.pop();
        int mid = division(nums, l, r);
        // 将新的序列区间入栈.
        if (l < mid - 1) {
            st.push(l);
            st.push(mid - 1);
        }
        if (r > mid + 1) {
            st.push(mid + 1);
            st.push(r);
        }
    }

}

void DiguiQuickSort(vector<int> &nums, int left, int right)//递归
{
    // 外层if的目的是当划分到最小单位时，作为递归退出条件
    if (left < right) {
        int mid = division(nums, left, right);
        DiguiQuickSort(nums, left, mid - 1);
        DiguiQuickSort(nums, mid + 1, right);
    }
}


int Partition(vector<int> &arr, int L, int R) {//传引用
    int pivot = arr[L + rand() % (R - L + 1)];
    int i = L - 1, j = R + 1;
    while (1) {
        do ++i; while (arr[i] < pivot);//不能取等号，取等号可能越界
        do --j; while (arr[j] > pivot);
        if (i >= j) return j;//j右边都大于等于pivot，j左边(包括j)都小于等于pivot
        swap(arr[i], arr[j]);
    }
}

void YouhuaQuickSort(vector<int> &arr, int L, int R)//改进尾递归优化
{
    while (L < R) {
        int mid = Partition(arr, L, R);
        if (mid - L < R - mid) {
            YouhuaQuickSort(arr, L, mid);
            L = mid + 1;
        } else {
            YouhuaQuickSort(arr, mid + 1, R);
            R = mid;
        }
    }

}

void shellSort(vector<int> &v) {
    int size = (int) v.size();
    if (size < 2) return;
    int incre = size / 2;
    int temp;
    for (; incre >= 1; incre /= 2) {
        for (int i = incre; i < size; ++i) {
            int j = i - incre;
            temp = v[i];
            while (j >= 0 && temp < v[j]) {
                v[j + incre] = v[j];
                j -= incre;
            }
            v[j + incre] = temp;
        }
    }
}

int mainTest() {
    ifstream infile(R"(D:\rubbish\suiji.txt)");
    vector<int> iVec;
    string strTmp;
    int iTmp = 0;
    if (!infile) {
        return -1;
    }
    while (getline(infile, strTmp, ' '))    // 以空格为分隔符，读取每一个词
    {
        if (JudgeNum(strTmp, iTmp)) {
            iVec.push_back(iTmp);
        }
    }
    vector<int>::size_type stCnt = iVec.size();
    for (int i = 0; i < stCnt; i++)
        infile >> iVec.at(i);
    infile.close();
    double start, finish;
    start = (double) clock(); //获得开始的时间
    //shellSort(iVec);
    // DiguiQuickSort(iVec, 0, iVec.size() - 1);
    FeidiguiQuickSort(iVec);
    // YouhuaQuickSort(iVec, 0, iVec.size() - 1);
    finish = (double) clock(); //获得结束的时间
    //然后输出 时间差秒数：
    printf("%.5f ms", finish - start);
    cout << endl;
    int n = iVec.size();
    cout << n << endl;//数据个数


}